using BepuUtilities.Collections;
using BepuUtilities.Memory;
using System;
using System.Diagnostics;
using System.Runtime.CompilerServices;
#if MYCODE
using BepuUtilities.Vectors;
#else
#endif
namespace BepuPhysics.Trees
{
    public struct SubtreeHeapEntry
    {
        public int Index;
        public float Cost;
    }
    unsafe internal struct SubtreeBinaryHeap
    {
        public SubtreeHeapEntry* Entries;
        public int Count;

        public SubtreeBinaryHeap(SubtreeHeapEntry* entries)
        {
            Entries = entries;
            Count = 0;
        }


        public unsafe void Insert(ref Node node, ref QuickList<int> subtrees)
        {
            ref var children = ref node.A;
            for (int childIndex = 0; childIndex < 2; ++childIndex)
            {
                ref var child = ref Unsafe.Add(ref children, childIndex);
                if (child.Index >= 0)
                {
                    int index = Count;
                    var cost = Tree.ComputeBoundsMetric(ref child.Min, ref child.Max);// -Node->PreviousMetric;
                    ++Count;

                    // 往上筛。
                    while (index > 0)
                    {
                        var parentIndex = (index - 1) >> 1;
                        var parent = Entries + parentIndex;
                        if (parent->Cost < cost)
                        {
                            // 将父对象拉下。
                            Entries[index] = *parent;
                            index = parentIndex;
                        }
                        else
                        {
                            // 找到插入点了。
                            break;
                        }
                    }
                    var entry = Entries + index;
                    entry->Index = child.Index;
                    entry->Cost = cost;

                }
                else
                {
                    // 立即添加叶节点。
                    subtrees.AddUnsafely(child.Index);
                }
            }

        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        void Pop(out SubtreeHeapEntry entry)
        {
            entry = Entries[0];
            --Count;
            var cost = Entries[Count].Cost;

            // 把这些元素向上拉,把空隙填满。
            int index = 0;
            while (true)
            {
                var childIndexA = (index << 1) + 1;
                var childIndexB = (index << 1) + 2;
                if (childIndexB < Count)
                {
                    // 两个孩子都有空。
                    // 试着和最大的那个换一下。
                    var childA = Entries + childIndexA;
                    var childB = Entries + childIndexB;
                    if (childA->Cost > childB->Cost)
                    {
                        if (cost > childA->Cost)
                        {
                            break;
                        }
                        Entries[index] = Entries[childIndexA];
                        index = childIndexA;
                    }
                    else
                    {
                        if (cost > childB->Cost)
                        {
                            break;
                        }
                        Entries[index] = Entries[childIndexB];
                        index = childIndexB;
                    }
                }
                else if (childIndexA < Count)
                {
                    // 只有一个孩子有空。
                    var childA = Entries + childIndexA;
                    if (cost > childA->Cost)
                    {
                        break;
                    }
                    Entries[index] = Entries[childIndexA];
                    index = childIndexA;
                }
                else
                {
                    // 孩子们超出了人群的范围。
                    break;
                }
            }
            // 将最后一个条目移到适当位置。
            Entries[index] = Entries[Count];

        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public bool TryPop(ref Buffer<Metanode> metanodes, ref int remainingSubtreeSpace, ref QuickList<int> subtrees, out int index, out float cost)
        {
            while (Count > 0)
            {
                // 反复弹出最小尺寸,直到找到合适的为止。
                // 考虑到独一无二的访问特性,在空间不多的情况下销毁堆并不重要。
                // 如果您消耗了所有节点,这只是意味着子树集合中不再有适合的条目。
                Pop(out SubtreeHeapEntry entry);
                // 选择是否展开此节点。
                // 只有在它的孩子适合的情况下,才会选择扩张。
                // 任何时候展开节点时,现有节点都会从priorityQueue中存储的潜在子树集中删除。
                // 因此,reminingSubtreeSpace=maxumSubtreesCount-(priorityQueue.Count+subtrees.Count)中的更改是Child Count-1。
                // 情况一直都是这样。
                if (remainingSubtreeSpace >= 1 && metanodes[entry.Index].RefineFlag == 0)
                {
                    // Debug.Fail("别忘了重新启用细化标志条件");
                    // 此节点的子节点可以成功包含在剩余空间中。
                    index = entry.Index;
                    cost = entry.Cost;
                    remainingSubtreeSpace -= 1;
                    return true;
                }
                else
                {
                    // 此节点的子节点不适合,或者它是优化目标。细化目标不能展开。
                    // 因为我们以后找不到它,所以现在需要添加它。
                    // 我们将前一个条目从队列中弹出,因此剩余的SubtreeSpace不会因为重新添加它而改变。
                    // (RemainingSubtreeSpace=maxumSubtreesCount-(PriorityQueue.Count+subtrees.Count))
                    subtrees.AddUnsafely(entry.Index);
                }
            }
            index = -1;
            cost = -1;
            return false;
        }
    }

    partial struct Tree
    {

        public unsafe void CollectSubtrees(int nodeIndex, int maximumSubtrees, SubtreeHeapEntry* entries,
            ref QuickList<int> subtrees, ref QuickList<int> internalNodes, out float treeletCost)
        {

            // 通过重复选择成本最高的子树来迭代收集子树。
            // 这会一次收集给定节点的每个子节点-子树集不能只包括节点的一些子节点。

            // (您可以取消此限制,只获取一些节点,但这会使事情复杂化。你不能简单地移除
            // 父级并添加其子级以进行更深入的研究;这将需要对构造结果进行一些后期修正
            // 或者可能限制生成过程为未受影响的节点留出空间。)


            ref var node = ref Nodes[nodeIndex];
            Debug.Assert(maximumSubtrees >= 2, "Can't only consider some of a node's children, but specified maximumSubtrees precludes the treelet root's children.");
            // 所有树根的子代都会立即包括在内。(遵循上述要求。)

            var priorityQueue = new SubtreeBinaryHeap(entries);

            priorityQueue.Insert(ref node, ref subtrees);

            // 请注意,树根不会添加到内部节点列表中。

            // 请注意,树根的成本不包括在treeleCost中。
            // 那是因为小树根是不会改变的。
            treeletCost = 0;
            int remainingSubtreeSpace = maximumSubtrees - priorityQueue.Count - subtrees.Count;
            while (priorityQueue.TryPop(ref Metanodes, ref remainingSubtreeSpace, ref subtrees, out int highestIndex, out float highestCost))
            {
                treeletCost += highestCost;
                internalNodes.AddUnsafely(highestIndex);

                // 将所有子项添加到子树集中。
                // 这是安全的,因为我们预先验证了节点中的子节点数量。
                ref var expandedNode = ref Nodes[highestIndex];
                priorityQueue.Insert(ref expandedNode, ref subtrees);
            }

            for (int i = 0; i < priorityQueue.Count; ++i)
            {
                subtrees.AddUnsafely(priorityQueue.Entries[i].Index);
            }

            // 对内部节点进行排序,以便深度优先构建器倾向于生成较少的缓存置乱结果。
            // TODO：请注意,节点索引中的值范围通常限制在65535以下的值。换句话说,基数排序将是一个重大的胜利。
            // 更好的是,使用某种形式的隐式缓存优化来消除不连续的内部节点的可能性,以便整个收集过程
            // 归结为根据根索引和叶数计算一系列元素。处理根节点稍微复杂一些。
            // 我怀疑这整个功能稍后会消失。例如：
            // 始终运行的内部多线程根构建器,将一组子树视为树叶,然后进行外部多线程子树优化。
            // 根构建器会将其节点写出到一个新的内存挡路中,而不是就地工作。
            // 如果根构建器以一组已知叶数和已知位置的子树终止,则将在连续区域上执行多线程细化。
            // 换句话说,在任何时候都不需要某种目标节点,因为它们都是以解析方式计算的,并且已知它们位于缓存中的最佳位置。
            if (internalNodes.Count > 0) // 如果目标节点的两个子节点都是叶子,则可能没有内部节点。
            {
                var comparer = new PrimitiveComparer<int>();
                QuickSort.Sort(ref internalNodes[0], 0, internalNodes.Count - 1, ref comparer);
            }
        }


        unsafe void ValidateStaging(Node* stagingNodes, ref QuickList<int> subtreeNodePointers, int treeletParent, int treeletIndexInParent, BufferPool pool)
        {
            var collectedSubtreeReferences = new QuickList<int>(subtreeNodePointers.Count, pool);
            var internalReferences = new QuickList<int>(subtreeNodePointers.Count, pool);
            internalReferences.Add(0, pool);
            ValidateStaging(stagingNodes, 0, ref subtreeNodePointers, ref collectedSubtreeReferences, ref internalReferences, pool, out int foundSubtrees, out int foundLeafCount);
            if (treeletParent < -1 || treeletParent >= nodeCount)
                throw new Exception("Bad treelet parent.");
            if (treeletIndexInParent < -1 || (treeletParent >= 0 && treeletIndexInParent >= 2))
                throw new Exception("Bad treelet index in parent.");
            if (treeletParent >= 0 && Unsafe.Add(ref Nodes[treeletParent].A, treeletIndexInParent).LeafCount != foundLeafCount)
            {
                throw new Exception("Bad leaf count.");
            }
            if (subtreeNodePointers.Count != foundSubtrees)
            {
                throw new Exception("Bad subtree found count.");
            }
            for (int i = 0; i < collectedSubtreeReferences.Count; ++i)
            {
                if (!subtreeNodePointers.Contains(collectedSubtreeReferences[i]) || !collectedSubtreeReferences.Contains(subtreeNodePointers[i]))
                    throw new Exception("Bad subtree reference.");
            }
            collectedSubtreeReferences.Dispose(pool);
            internalReferences.Dispose(pool);
        }
        unsafe void ValidateStaging(Node* stagingNodes, int stagingNodeIndex,
            ref QuickList<int> subtreeNodePointers, ref QuickList<int> collectedSubtreeReferences,
            ref QuickList<int> internalReferences, BufferPool pool, out int foundSubtrees, out int foundLeafCount)
        {
            var stagingNode = stagingNodes + stagingNodeIndex;
            var children = &stagingNode->A;
            foundSubtrees = foundLeafCount = 0;
            for (int i = 0; i < 2; ++i)
            {
                ref var child = ref children[i];
                if (child.Index >= 0)
                {
                    if (internalReferences.Contains(child.Index))
                        throw new Exception("A child points to an internal node that was visited. Possible loop, or just general invalid.");
                    internalReferences.Add(child.Index, pool);
                    ValidateStaging(stagingNodes, child.Index, ref subtreeNodePointers, ref collectedSubtreeReferences, ref internalReferences, pool, out int childFoundSubtrees, out int childFoundLeafCount);

                    if (childFoundLeafCount != child.LeafCount)
                        throw new Exception("Bad leaf count.");
                    foundSubtrees += childFoundSubtrees;
                    foundLeafCount += childFoundLeafCount;
                }
                else
                {
                    var subtreeNodePointerIndex = Encode(child.Index);
                    var subtreeNodePointer = subtreeNodePointers[subtreeNodePointerIndex];
                    // 不需要在混乱的SweepSubtree中查找信息,只需返回源代码即可。
                    if (subtreeNodePointer >= 0)
                    {
                        ref var node = ref Nodes[subtreeNodePointer];
                        var totalLeafCount = 0;
                        for (int childIndex = 0; childIndex < 2; ++childIndex)
                        {
                            totalLeafCount += Unsafe.Add(ref node.A, childIndex).LeafCount;
                        }

                        if (child.LeafCount != totalLeafCount)
                            throw new Exception("bad leaf count.");
                        foundLeafCount += totalLeafCount;
                    }
                    else
                    {
                        var leafIndex = Encode(subtreeNodePointer);
                        if (child.LeafCount != 1)
                            throw new Exception("bad leaf count.");
                        foundLeafCount += 1;
                    }
                    ++foundSubtrees;
                    collectedSubtreeReferences.Add(subtreeNodePointer, pool);
                }
            }

        }

    }
}
